#include<iostream>
#include<vector>
using namespace std;
/*
给定一个有 n 个节点的有向无环图，用二维数组 graph 表示，请找到所有从 0 到 n-1 的路径并输出（不要求按顺序）。
graph 的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些结点
（译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a ），若为空，就是没有下一个节点了。
*/
vector<int> path;
vector<vector<int>> result;
void dfs(vector<vector<int>>& graph,int x)
{
    if(x==graph.size()-1)
    {
        result.push_back(path);
        return;
    }
    for(int i=0;i<graph[x].size();i++)
    {
        path.push_back(graph[x][i]);
        dfs(graph,graph[x][i]);
        path.pop_back();
    }
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
    path.push_back(0);
    dfs(graph,0);
    return result;
}
int main()
{
    vector<vector<int>> graph = {{1,2},{3},{3},{}};
    vector<vector<int>> result = allPathsSourceTarget(graph);
    for(int i=0;i<result.size();i++)
    {
        for(int j=0;j<result[i].size();j++)
        {
            cout<<result[i][j]<<" ";
        }
        cout<<endl;
    }
}